/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/substring-with-concatenation-of-all-words
   @Language: C++
   @Datetime: 19-05-31 17:32
   */

// Method 1, Time 824ms, Space 289MB
class Solution {
public:
	vector<int> findSubstring(string s, vector<string>& words) {
		vector<int> v;
		if(words.size()==0 || words[0].length()==0) return v;
		int len=words[0].length(), win=len*words.size();
		if(s.length()<win) return v;
		unordered_map<string,int> freqs;
		for(int i=words.size(); i--; ++freqs[words[i]]);
		for(int i=0; i+win<=s.length(); ++i){
			auto tmp=freqs;
			bool found=true;
			for(int j=i, k=words.size(); found && k--; j+=len)
				if(0==tmp[s.substr(j,len)]--) found=false;
			if(found) v.push_back(i);
		}
		return v;
	}
};

// Method 2, Time 480ms, Space 107MB
class Solution {
public:
	vector<int> findSubstring(string &s, vector<string>& words) {
		vector<int> v;
		if(words.size()==0 || words[0].length()==0) return v;
		int len=words[0].length(), win=len*words.size();
		if(s.length()<win) return v;
		sort(words.begin(),words.end());
		unordered_map<int,int> freqs;	// id, freq
		for(int i=0, cnt=0; i<words.size(); i+=cnt){
			for(cnt=0; i+cnt<words.size() && words[i].compare(words[i+cnt])==0; ++cnt);
			freqs[i]=cnt;
		}
		unordered_map<string,int> ids;	// word, id
		for(int i=words.size(); i--; ids[words[i]]=i);
		unordered_map<int,int> maps;	// s-id, words-id
		for(int i=0; i+len<=s.length(); ++i){
			const auto f=ids.find(s.substr(i,len));
			if(f!=ids.end()) maps[i]=f->second;
			else maps[i]=-1;
		}

		for(int i=0, lastid=-1; i+win<=s.length(); ++i){
			if(lastid!=-1 && lastid>i && (lastid-i)%len==0) continue;
			auto tmp=freqs;
			bool found=true;
			for(int j=i, k=words.size(); found && k--; j+=len){
				const int &id=maps[j];
				if(id==-1) {
					found=false;
					lastid=j;
				}
				else if(0==tmp[id]--) found=false;
			}
			if(found) v.push_back(i);
		}
		return v;
	}
};
